# 动态规划50题 https://www.bilibili.com/video/BV1aa411f7uT
# 7/50 打家劫舍II
# leetcode第213题: https://leetcode.cn/problems/house-robber/description/

def rob(nums: list[int]) -> int:
    """为了记录选择首还是尾, 需要使用一个二维线性方程:
    其中dp[0][i]表示在选择首部的元素情况下, 到第i个房间时可以获得的最大值; dp[1][i]表示选择尾部的最大值
    """
    n = len(nums)
    if n < 2:
        return nums[0]
    if n == 2:
        return max(nums[0], nums[1])
    # dp = [[0] * 5] * 2
    # dp[0][1] = 5  仅对第一行的第二个元素赋值
    # print(dp) # 输出: [[0, 5, 0, 0, 0], [0, 5, 0, 0, 0]]
    # 可以看到第二行的第一个元素的值也会修改, 这是因为这样的声明方法会导致多行使用了同一个引用
    # 所以需要使用下面的引用方法才可以
    dp = [[0 for _ in range(n)] for _ in range(2)]
    dp[0][0] = nums[0]  # 选择首部
    dp[0][1] = nums[0]
    dp[1][0] = 0  # 选择尾部
    dp[1][1] = nums[1]
    for i in range(2, n):
        dp[0][i] = max(dp[0][i - 1], dp[0][i - 2] + nums[i])
        dp[1][i] = max(dp[1][i - 1], dp[1][i - 2] + nums[i])
    return max(dp[0][n - 2], dp[1][n - 1])


if __name__ == '__main__':
    nums = [2, 3, 2]  # 3
    print(rob(nums))
    nums1 = [1, 2, 3, 1]  # 4
    print(rob(nums1))
    nums2 = [1, 2, 3]  # 3
    print(rob(nums2))
    nums3 = [0, 0]  # 0
    print(rob(nums3))
    nums4 = [200, 3, 140, 20, 10]  # 340
    print(rob(nums4))
    nums5 = [4, 1, 2, 7, 5, 3, 1]  # 4 + 7 + 3 = 14
    print(rob(nums5))
